DMS Colloquium: Dr. Songling Shan

Speaker: Dr. Songling Shan, Vanderbilt University

Title: Chvátal's Toughness Conjecture and Related Problems

Abstract: Introduced by Chvátal in 1973, toughness is a measure of graph connectivity and "resilience'' under removal of vertices. It is well known that every cycle is 1-tough. Conversely, Chvátal conjectured that there is a constant $t_0$ such that every $t_0$-tough graph contains a Hamiltonian cycle (Chvátal's Toughness Conjecture). The construction of Bauer, Broersma, and Veldman in 2000 shows that $t_0$ should be at least $\frac{9}{4}$ if exists.  In this talk, I will survey  progress toward  Chvátal's Toughness Conjecture and results about toughness conditions that guarantee the existence of more general spanning structures in a graph.